import java.util.Arrays;

public class Floyd {

    private static char[] vertexData;
    private int[][] dis;// 记录最短路径
    private int[][] pre;// 记录前驱顶点

    public Floyd(char[] vertexData, int[][] weight) {
        this.vertexData = vertexData;
        this.dis = weight;
        this.pre = new int[vertexData.length][vertexData.length];
        for (int i = 0; i < pre.length; i++) {
            Arrays.fill(pre[i], i);
        }

    }

    public void floydAlgorithm() {
        int len = 0;
        for (int k = 0; k < dis.length; k++) {
            for (int i = 0; i < dis.length; i++) {
                for (int j = 0; j < dis.length; j++) {
                    len = dis[i][k] + dis[k][j];
                    if (len < dis[i][j]) {
                        dis[i][j] = len;
                        pre[i][j] = pre[k][j];
                    }
                }
            }
        }
    }

    public void showRoad() {
        for (int i = 0; i < dis.length; i++) {
            for (int j = 0; j < dis.length; j++) {
                System.out.println(vertexData[i] + "->" + vertexData[j] + ":" + dis[i][j] + " ");
            }
            System.out.println();
        }
    }

}
